//
// Created by 鲁婷婷 on 2021/10/16.
//

#include <iostream>
#include <cstdlib>
#include<ctime>
using namespace std;
#define maxGen 45 //最大进化代数
#define popSize 20//种群数目
#define  crossP 0.3 //交叉概率
#define  mutationP 0.2//变异概率
#define chromLen 5//染色体长度，即为城市个数
int Distance[chromLen][chromLen]={{0,  7,  6, 10, 13},
                                  {7,  0,  7, 10, 10},
                                  {6,  7,  0, 5,  9},
                                  {10, 10, 5, 0,  11},
                                  {13, 10, 9, 11, 0}};

int population[popSize][chromLen];//种群
int bestResult[chromLen];//最短路径
int minDistance;
// 函数声明
void init(); // 种群初始化函数
int* min(int*); // 计算距离数组的最小值
int path_len(int*); // 计算某一个方案的路径长度，适应度函数为路线长度的倒数
void Choice(int [popSize][chromLen]); // 选择操作
void Cross(int [popSize][chromLen]); // 交叉操作
void Mutation(int [popSize][chromLen]); // 变异操作

//种群初始化
void init()
{
    int num = 0;
    while(num < popSize)//通过交换位置产生初始个体
    {
        for(int i=0; i < popSize; i++)
            for(int j=0; j < chromLen; j++)
                population[i][j] = j + 1;
        num++;
        for(int i=0; i < chromLen - 1; i++)
        {
            for(int j=i+1; j < chromLen; j++)
            {
                int temp = population[num][i];
                population[num][i]=population[num][j];
                population[num][j] = temp;
                num++;
                if(num >= popSize)
                    break;
            }
            if(num >= popSize)
                break;
        }
        //若依旧无法产生足够初始个体，选择两个基因位置进行交换
        while(num < popSize)
        {
            double r1 = ((double)rand())/(RAND_MAX+1.0);
            double r2 = ((double)rand())/(RAND_MAX+1.0);
            int pos1 = (int)(chromLen * r1); // 位置1
            int pos2 = (int)(chromLen * r2); // 位置2
            int temp = population[num][pos1];
            population[num][pos1] = population[num][pos2];
            population[num][pos2] = temp;    // 交换基因位置
            num++;
        }
    }
}
//获得种群里最小的距离和这个种群的下标
int* min(int* arr){
    static int bestIndex[2];
    int minDis = arr[0];
    int minIndex = 0;
    for(int i=1; i < popSize; i++)
    {
        int dis = arr[i];
        if(dis < minDis)
        {
            minDis = dis;
            minIndex = i;
        }
    }
    bestIndex[0] = minIndex;
    bestIndex[1] = minDis;
    return bestIndex;
}

//计算路径长度
int path_len(int* arr)
{
    int path = 0;
    //int index = *arr;
    for(int i=0; i < chromLen - 1; i++)
    {
        int index1 = *(arr+i)-1;
        int index2 = *(arr+i+1)-1;
        path += Distance[index1][index2];
    }
    int lastIndex = arr[chromLen - 1] - 1;
    int firstIndex = arr[0]-1;
    path += Distance[lastIndex][firstIndex];
    return path;//总路径长度
}

//选择操作
void Choice(int chrom[popSize][chromLen])
{
    double pick;
    int choiceArr[popSize][chromLen];
    double fitPro[popSize];
    double sum = 0;
    double fit[popSize];//适应度函数数组
    for(int j=0; j < popSize; j++)
    {
        int path = path_len(chrom[j]);
        double fitness = 1/(double)path;
        fit[j] = fitness;
        sum += fitness;
    }
    for(int j = 0; j < popSize; j++)
    {
        fitPro[j] = fit[j] / sum;//概率数组，适应度越高，被选中的概率越大
    }
    //轮盘赌
    for(int i = 0; i < popSize; i++)
    {
        pick = ((double)rand())/(double)RAND_MAX;
        for(int j = 0; j < popSize; j++)
        {
            pick = pick - fitPro[j];
            if(pick<=0)
            {
                for(int k = 0; k < chromLen; k++)
                    choiceArr[i][k] = chrom[j][k];//选择一个个体
                break;
            }
        }
    }
    for(int i=0; i < popSize; i++)
    {
        for(int j=0; j < chromLen; j++)
            chrom[i][j] = choiceArr[i][j];
    }
}

//交叉操作
void Cross(int chrom[popSize][chromLen])
{
    double pick;
    double pick1,pick2;
    int choice1,choice2;
    int pos1,pos2;
    int temp;
    int conflict1[chromLen];//冲突位置
    int conflict2[chromLen];
    int num1,num2=0;
    int index1,index2;
    int move = 0;//当前移动位置
    while(move < popSize - 1)//???
    {
        pick = ((double)rand())/RAND_MAX;//用于决定此次是否进行交叉
        if(pick > crossP)
        {
            move += 2;
            continue;//此次不进行交叉
        }
        //采用部分映射杂交
        choice1 = move;//杂交的两个父代
        choice2 = move+1;//小心下标越界
        pick1 = ((double)rand())/(RAND_MAX+1.0);
        pick2 = ((double)rand())/(RAND_MAX+1.0);
        pos1 = (int)(pick1 * chromLen); // 用于确定两个杂交点的位置
        pos2 = (int)(pick2 * chromLen);
        while(pos1 > chromLen - 2 || pos1 < 1)
        {
            pick1 = ((double)rand())/(RAND_MAX+1.0);
            pos1 = (int)(pick1 * chromLen);
        }
        while(pos2 > chromLen - 2 || pos2 < 1)
        {
            pick2 = ((double)rand())/(RAND_MAX+1.0);
            pos2 = (int)(pick2 * chromLen);
        }
        if(pos1 > pos2)
        {
            temp = pos1;
            pos1 = pos2;
            pos2 = temp; // 交换pos1和pos2的位置
        }
        for(int j=pos1;j<=pos2;j++)
        {
            temp = chrom[choice1][j];
            chrom[choice1][j] = chrom[choice2][j];
            chrom[choice2][j] = temp;
        }
        num1 = 0;
        num2 = 0;
        if(pos1 > 0 && pos2 < chromLen - 1)
        {
            for(int j = 0;j<=pos1-1;j++)
            {
                for(int k = pos1;k<=pos2;k++)
                {
                    if(chrom[choice1][j]==chrom[choice1][k])
                    {
                        conflict1[num1]=j;
                        num1++;
                    }
                    if(chrom[choice2][j]==chrom[choice2][k])
                    {
                        conflict2[num2] = j;
                        num2++;
                    }
                }
            }
            for(int j=pos2+1; j < chromLen; j++)
            {
                for(int k=pos1;k<=pos2;k++)
                {
                    if(chrom[choice1][j]==chrom[choice1][k])
                    {
                        conflict1[num1] = j;
                        num1++;
                    }
                    if(chrom[choice2][j] == chrom[choice2][k])
                    {
                        conflict2[num2] = j;
                        num2++;
                    }
                }
            }
        }
        if ((num1 == num2) && num1 > 0)
        {
            for(int j=0;j<num1;j++)
            {
                index1 = conflict1[j];
                index2 = conflict2[j];
                temp = chrom[choice1][index1]; // 交换冲突的位置
                chrom[choice1][index1] = chrom[choice2][index2];
                chrom[choice2][index2] = temp;
            }
        }
        move += 2;
    }
}

//变异操作，随机选取两个点，兑换位置
void Mutation(int chrom[popSize][chromLen])
{
    double pick,pick1,pick2;
    int pos1,pos2,temp;
    for(int i=0; i < popSize; i++)
    {
        pick= ((double)rand())/RAND_MAX; // 用于判断是否进行变异操作
        if(pick > mutationP)
            continue;
        pick1 = ((double)rand())/(RAND_MAX+1.0);
        pick2 = ((double)rand())/(RAND_MAX+1.0);
        pos1=(int)(pick1 * chromLen);
        pos2=(int)(pick2 * chromLen);
        while (pos1 > chromLen - 1) {
            pick1 = ((double) rand()) / (RAND_MAX + 1.0);
            pos1 = (int) (pick1 * chromLen);
        }
        while (pos2 > chromLen - 1) {
            pick2 = ((double) rand()) / (RAND_MAX + 1.0);
            pos2 = (int) (pick2 * chromLen);
        }
        temp = chrom[i][pos1];
        chrom[i][pos1] = chrom[i][pos2];
        chrom[i][pos2] = temp;
    }
}

int main() {
    time_t start,finish;
    start = clock();
    srand((unsigned)time(NULL));
    init();//初始化种群

    int bestFitIndex = 0;
    int totalDistance[popSize];
    int dis;
    for(int j=0; j < popSize; j++)
    {
        dis = path_len(population[j]);
        totalDistance[j] = dis;
    }
    int* best = min(totalDistance);
    minDistance=*(best + 1);
    int index=*(best);
    for(int j=0; j < chromLen; j++)
        bestResult[j] = population[index][j];
    //开始进化

    int* newBest;
    int newMinDis;
    int newIndex;
    for(int i=0; i < maxGen; i++)
    {
        Choice(population);
        Cross(population);
        Mutation(population);
        for(int j=0; j < popSize; j++)
            totalDistance[j]= path_len(population[j]);
        newBest=min(totalDistance);
        newMinDis=*(newBest + 1);
        if(newMinDis < minDistance)
        {
            minDistance = newMinDis;
            newIndex=*newBest;
            for(int j=0; j < chromLen; j++)
            {
                bestResult[j]=population[newIndex][j];
            }
            cout<<endl;
            bestFitIndex= i + 1;
        }
    }
    finish=clock();
    double duration = ((double)(finish-start))/CLOCKS_PER_SEC; // 计算耗时

    cout << "此次使用遗传算法解决规模为" << chromLen << "的TSP问题，种群数目为" << popSize << "进化代数为" << maxGen << endl;
    cout<<"最短路径为：";
    for(int i=0; i < chromLen; i++)
        cout << bestResult[i] << "--->";
    cout << bestResult[0] << endl;
    cout << "该路径长度为:" << minDistance << endl;
    cout << "该路径在第" << bestFitIndex << "代" << endl;
    cout<<"程序耗时："<<duration<<endl;
    return 0;
}
